package com.company.Sort;

import java.util.Arrays;
import java.util.Collections;

public class Sort {
    private Sort(){}


    public static <T extends Comparable<T>> void bubbleSort(T[] array){
        if(array==null) return;

        for(int i=1;i<array.length;i++){
            int z=0;

            for(int j=0;j<array.length-1;j++){
                if(array[j].compareTo(array[j+1])>0){
                    T t=array[j];
                    array[j]=array[j+1];
                    array[j+1]=t;
                    z=1;
                }
            }

            if(z==0) break;
        }
    }

    public static <T extends Comparable<T>> void mergeSort(T[] array){
        T[] newArray=array.clone();
        merge(array,newArray,0,array.length-1);
    }
    private static <T extends Comparable<T>> void merge(T[] array,T[] newArray,int left,int right){
        if(left==right) return;
        int center=(left+right)/2;
        merge(array,newArray,left,center);
        merge(array,newArray,center+1,right);

        int i=left,j=center+1,point=left;

        while (i<=center&&j<=right){
            if(array[i].compareTo(array[j])<0){
                newArray[point]=array[i];
                point++;
                i++;
            }else {
                newArray[point]=array[j];
                point++;
                j++;
            }
        }

        while (i<=center){
            newArray[point]=array[i];
            i++;
            point++;
        }



        while (j<=right){
            newArray[point]=array[j];
            j++;
            point++;
        }

        System.arraycopy(newArray,left,array,left,right-left+1);
    }

    public static <T extends Comparable<T>> void quickSort(T[] array){
        quickSort(array,0,array.length-1);
    }
    private static <T extends Comparable<T>> void quickSort(T[] array,int low,int high){
        if(high>low){
            int current=patition(array,low,high);
            quickSort(array,low,current-1);
            quickSort(array,current+1,high);
        }
    }
    private static <T extends Comparable<T>> int patition(T[] array,int low,int high){
        T pivor=array[low];
        int first=low;
        low+=1;

        while (high>low){
            while (high>=low&&array[low].compareTo(pivor)<=0){
                low++;
            }

            while (high>=low&&array[high].compareTo(pivor)>0){
                high--;
            }

            if(high>low){
                T t=array[high];
                array[high]=array[low];
                array[low]=t;
            }
        }

        if(pivor.compareTo(array[high])>0){
            array[first]=array[high];
            array[high]=pivor;
            return high;
        }else {
            return first;
        }
    }

    public static void main(String[] args) {
        Integer[] a={1,4,6,2,3,7,4,13,8,9};

        quickSort(a);

        for(int i=0;i<a.length;i++){
            System.out.println(a[i]);
        }
    }


}